package sorting;

import java.util.Arrays;

public class ShellSort {

    /**
     * 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
     * 按增量序列个数k，对序列进行k 趟排序；
     * 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
     */

    public static void main(String[] args) {

        int[] targetArr = {5, 1, 17, 16, 60, 64, 33, 21, 7};
        System.out.println(Arrays.toString(shellsort(targetArr)));
    }

    public static int[] shellsort(int targetArr[]) {

        int[] arr = Arrays.copyOf(targetArr, targetArr.length);

        int tmp, len = arr.length;
        int gap = len / 2;

        while (gap > 0) {

            for (int i = 1; i < arr.length; i++) {
                tmp = arr[i];
                int preIndex = i - gap;

                while (preIndex >= 0 && arr[preIndex] > tmp) {
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex -= gap;
                }
                arr[preIndex + gap] = tmp;
            }
            gap /= 2;
        }

        return arr;
    }
}
